package 题目集.位运算.集合论;

import org.junit.Test;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/number-of-bit-changes-to-make-two-integers-equal/description/
 * <p>
 * 给你两个正整数 n 和 k。
 * 你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。
 * 返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。
 */
public class ch02_使两个整数相等的位更改次数 {

    @Test
    public void test() {
        System.out.println(minChanges(13, 4));
    }

    public int minChanges(int n, int k) {
        /*n不是k的父集，所以删多少次都不会为k*/
        if ((n | k) != n) return -1;
        return bitCnt(n) - bitCnt(k);
    }

    /**
     * 求v中为1的bit有多少个
     */
    public int bitCnt(int v) {
        int cnt = 0;
        for (; v > 0; v -= v & -v) { // v & -v是lowbit操作
            cnt++;
        }
        return cnt;
    }
}
